package leetcode.backtrace;

import java.util.*;

/**
 * @Description
 * @Author 26233
 * @Create 2021-04-18 11:29:25
 */


/*
给定两个单词（beginWord 和 endWord）和一个字典 wordList，找出所有从 beginWord 到 endWord 的最短转换序列。转换需遵循如下规则：

每次转换只能改变一个字母。
转换后得到的单词必须是字典中的单词。
说明:

如果不存在这样的转换序列，返回一个空列表。
所有单词具有相同的长度。
所有单词只由小写字母组成。
字典中不存在重复的单词。
你可以假设 beginWord 和 endWord 是非空的，且二者不相同。
示例 1:

输入:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

输出:
[
  ["hit","hot","dot","dog","cog"],
  ["hit","hot","lot","log","cog"]
]
示例 2:

输入:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

输出: []

解释: endWord "cog" 不在字典中，所以不存在符合要求的转换序列。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/word-ladder-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法:
 1. 单词的变换过程是以beginWord为根的树形生长过程
 2. 以BFS的方式进行延伸和判断是否已到达endWord
    a. 如果已到达endWord，那么最短的变换过程即找到

 3. 递归的时候需要记录当前所有可能的路径，和已使用过的word
    a. 已使用过的word再变换的话只能增加长度，因此使用过的word不在考虑

 */

public class LeetCode126_FindLadders_Re {

    int minLen = Integer.MAX_VALUE;

    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {

        Set<String> usedWords = new HashSet<>();
        List<List<String>> result = new ArrayList<>();

        List<String> canChangeWord = getCanChangeWord(wordList, beginWord, usedWords);
        List<List<String>> currentPath = new ArrayList<>();

        canChangeWord.forEach(e -> {
            List<String> l = new ArrayList<>();
            l.add(beginWord);
            l.add(e);

            usedWords.add(e);
            currentPath.add(l);

            if (e.equals(endWord)){
                result.add(l);
            }

        });

        find(result, usedWords, currentPath, endWord, wordList);

        return result;
    }

    public void find(List<List<String>> result, Set<String> usedWords, List<List<String>> currentPath,
                     String endWord, List<String> wordList){
        boolean end = false;
        List<List<String>> newCurrentPath = new ArrayList<>();
        Set<String> tempUsed = new HashSet<>();
        for (List<String> path : currentPath){

            if (path.size() > minLen){
                return;
            }

            List<String> canChangeWord = getCanChangeWord(wordList, path.get(path.size() - 1), usedWords);

            if (canChangeWord.isEmpty()){
                continue;
            }

            for (String w : canChangeWord){
                tempUsed.add(w);
                List<String> newPath = new ArrayList<>(path);
                newPath.add(w);
                if (w.equals(endWord)){
                    if (newPath.size() < minLen){
                        if (!end){
                            result.clear();
                        }
                    }
                    end = true;
                    result.add(newPath);
                    minLen = newPath.size();
                    break;
                }

                newCurrentPath.add(newPath);
            }
        }
        usedWords.addAll(tempUsed);

        if (end || currentPath.isEmpty()){
            return;
        }

        find(result, usedWords, newCurrentPath, endWord, wordList);
    }

    public List<String> getCanChangeWord(List<String> wordList, String word, Set<String> usedWords){
        List<String> result = new ArrayList<>();
        for (String w : wordList){
            int diffCount = 0;
            if (!usedWords.contains(w)){
                int index = -1;
                while (++index < w.length()){
                    if (w.charAt(index) != word.charAt(index)){
                        diffCount++;
                    }
                }
                if (diffCount == 1){
                    result.add(w);
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        String beginWord = "hot";
        String endWord = "dog";
        // List<String> wordList = Arrays.asList("hot","dot","dog","lot","cog");
        //List<String> wordList = Arrays.asList("hot","dot","dog","lot","log","cog");
        List<String> wordList = Arrays.asList("hot","cog","dog","tot","hog","hop","pot","dot");
        //List<String> wordList = Arrays.asList("si","go","se","cm","so","ph","mt","db","mb","sb","kr","ln","tm","le","av","sm","ar","ci","ca","br","ti","ba","to","ra","fa","yo","ow","sn","ya","cr","po","fe","ho","ma","re","or","rn","au","ur","rh","sr","tc","lt","lo","as","fr","nb","yb","if","pb","ge","th","pm","rb","sh","co","ga","li","ha","hz","no","bi","di","hi","qa","pi","os","uh","wm","an","me","mo","na","la","st","er","sc","ne","mn","mi","am","ex","pt","io","be","fm","ta","tb","ni","mr","pa","he","lr","sq","ye");

        List<List<String>> ladders = new LeetCode126_FindLadders_Re().findLadders(beginWord, endWord, wordList);

        System.out.println("ladders = " + ladders);
    }


}
